package ljl.codetop;

import commons.TreeNode;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * 这个题做了得有四五遍了，还是不行，不会做
 */
public class _236_lowest_common_ancestor {

    /**
     * 先看自己和 p q 是不是一样，如果是直接返回自己，这就是答案？不对，如果另一个更考上，它才是答案
     * 然后递归到孩子那
     * 如果左右孩子都不是空，自己是结果，返回
     * 如果左边是空的，说明 p q 都在右边，怎么办？
     *
     * todo 我你妈？我居然蒙对了？
     */
    static class trytry {
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
            if (root == null) return null;
            TreeNode l = lowestCommonAncestor(root.left, p, q);
            TreeNode r = lowestCommonAncestor(root.right, p, q);
            // 随便找到一个就返回，因为是倒着找的，所以肯定先遇到小的后遇见大的
            if (root == p || root == q) return root;
            // 这个肯定没错
            if (l != null && r != null) return root;
            // 右边啥也没找到，左边有一个返回。这个应该就是答案
            if (l != null) return l;
            return r;
        }
    }

    static class lufei {
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
            if (root == null || root == p || root == q) return root;
            TreeNode l = lowestCommonAncestor(root.left, p, q), r = lowestCommonAncestor(root.right, p, q);
            return l != null ? r != null ? root : l : r;
        }
    }

    /**
     * 这个解法很好理解
     */
    static class off2 {
        Map<Integer, TreeNode> parent = new HashMap<>();
        Set<Integer> visited = new HashSet<>();

        public void dfs(TreeNode root) {
            if (root.left != null) {
                parent.put(root.left.val, root);
                dfs(root.left);
            }
            if (root.right != null) {
                parent.put(root.right.val, root);
                dfs(root.right);
            }
        }

        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
            dfs(root);
            while (p != null) {
                visited.add(p.val);
                p = parent.get(p.val);
            }
            while (q != null) {
                if (visited.contains(q.val)) {
                    return q;
                }
                q = parent.get(q.val);
            }
            return null;
        }
    }

    static class copy_off2 {
        Map<TreeNode, TreeNode> daddy = new HashMap<>();
        void dfs(TreeNode root) {
            if (root == null) return;
            if (root.left != null) {
                daddy.put(root.left, root);
                dfs(root.left);
            }
            if (root.right != null) {
                daddy.put(root.right, root);
                dfs(root.right);
            }
        }
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
            dfs(root);
            Set<TreeNode> path = new HashSet<>();
            while (p != null) {
                path.add(p);
                p = daddy.get(p);
            }
            while (q != null) {
                if (path.contains(q))
                    return q;
                q = daddy.get(q);
            }
            return null;
        }
    }
    
}
